package src.greed;

import java.util.Arrays;
import java.util.LinkedList;

public class no406 {//根据身高重建队列

    public int[][] reconstructQueue(int[][] people) {
        //按身高从大到小排序，身高相同按 k 升序排
        Arrays.sort(people, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];  //按 k 升序
            } else {
                return b[0] - a[0];  //按身高降序
            }
        });

        //不使用数组，因为数组每次插入元素是 O(n)。使用链表插入比较方便，链表每个元素是一个数组
        //int[][] res =new int[people.length][2];
        LinkedList<int[]> list = new LinkedList<>();
        for (int[] p : people) {
            list.add(p[1], p);  //在索引p[1]位置插入数组p
        }
        return list.toArray(new int[list.size()][]);
    }

}
